Định nghĩa P_(độ_phức_tạp)

Một ngôn ngữ L là trong P nếu và chỉ nếu tồn tại một máy Turing tất định M sao cho

  • Thời gian chạy của M là một đa thức của độ dài dữ liệu vào
  • Đối với tất cả x trong L, M cho kết quả 1
  • Đối với tất cả x không có trong L, M cho kết quả 0